package com.classicInterview;

/**
 * 求二叉树最长路径和
 *
 * @Author: huangzhigao
 * @Date: 2022/2/12 11:30
 */
public class MaxSumInTree {
    public class Node {
        private Node left;
        private Node right;
        private int value;
    }

    /**
     * 求解必须从头出发，到叶子节点的最大路径和
     *
     * @param head
     * @return
     */
    public int getMaxLengthFromHead(Node head) {
        if (head == null) {
            return 0;
        }
        return processFromHead(head);
    }


    /**
     * 以node为头，最大路径和为多少
     *
     * @param node
     * @return
     */
    public int processFromHead(Node node) {
        if (node.left == null && node.right == null) {
            return node.value;
        }

        int next = Integer.MIN_VALUE;
        if (node.left != null) {
            next = processFromHead(node.left);
        }

        if (node.right != null) {
            next = Math.max(next, processFromHead(node.right));
        }
        return next + node.value;
    }


    public class Info {
        private int allTreeMaxSum;
        private int fromHeadMaxSum;

        public Info(int allTreeMaxSum, int fromHeadMaxSum) {
            this.allTreeMaxSum = allTreeMaxSum;
            this.fromHeadMaxSum = fromHeadMaxSum;
        }

    }


    /**
     * 路径从任何节点出发，只能往下走，求最大路径和
     *
     * @param head
     * @return
     */
    public int MaxSum(Node head) {
        if (head == null) {
            return 0;
        }
        return process3(head).allTreeMaxSum;
    }

    /**
     * 1 与X无关，1左树整体最大，2右数整体最大
     * 2 与X有关，1 x自己，2 x往左走 3 x往右走
     *
     * @param x
     * @return
     */
    public Info process3(Node x) {
        if (x == null) {
            return null;
        }

        Info leftInfo = process3(x.left);
        Info rightInfo = process3(x.right);

        int p1 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p1 = leftInfo.allTreeMaxSum;
        }

        int p2 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p2 = leftInfo.allTreeMaxSum;
        }


        int p3 = x.value;

        int p4 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p4 = leftInfo.fromHeadMaxSum + x.value;
        }

        int p5 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p5 = rightInfo.fromHeadMaxSum + x.value;
        }

        int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(p4, p5));
        int fromHeadMaxSum = Math.max(p3, Math.max(p4, p5));
        return new Info(allTreeMaxSum, fromHeadMaxSum);
    }

    /**
     * 路径从任何节点出发，到达任意节点的最大路径和
     *
     * @param head
     * @return
     */
    public int MaxSum3(Node head) {
        if (head == null) {
            return 0;
        }
        return process4(head).allTreeMaxSum;
    }


    /**
     * 1 与X无关，1左树整体最大，2右数整体最大
     * 2 与X有关，1 x自己，2 x往左走 3 x往右走，4 x左+x右
     *
     * @param x
     * @return
     */
    public Info process4(Node x) {
        if (x == null) {
            return null;
        }

        Info leftInfo = process4(x.left);
        Info rightInfo = process4(x.right);

        int p1 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p1 = leftInfo.allTreeMaxSum;
        }

        int p2 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p2 = leftInfo.allTreeMaxSum;
        }


        int p3 = x.value;

        int p4 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p4 = leftInfo.fromHeadMaxSum + x.value;
        }

        int p5 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p5 = rightInfo.fromHeadMaxSum + x.value;
        }

        int p6 = Integer.MIN_VALUE;
        if (rightInfo != null && leftInfo != null) {
            p6 = rightInfo.fromHeadMaxSum + x.value + leftInfo.fromHeadMaxSum;
        }


        int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(p6, Math.max(p4, p5)));
        int fromHeadMaxSum = Math.max(p3, Math.max(p4, p5));
        return new Info(allTreeMaxSum, fromHeadMaxSum);
    }


}
